/*
面试题 02.04. 分割链表
link:https://leetcode.cn/problems/partition-list-lcci/
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/*
1. 创建两个带头单链表 sml_head big_head 和分别指向他们的指针sml_cur, big_cur、一个遍历原链表的指针cur
2. 比较cur->val 和 x
   a. cur->val < x 则把cur插入到sml_cur最后面
   b. cur->val >= x 则把cur插入到big_cur最后面
   c. cur = cur->next
3. 合并两个链表 sml_cur->next = big_head->next;
4. 返回链表 big_cur->next = NULL,sml_head->next;
*/ 
struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* sml_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* big_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* sml_cur, *big_cur, *cur;
    sml_cur = sml_head;
    big_cur = big_head;
    cur = head;
    while(cur)
    {
        if(cur->val < x){
            sml_cur->next = cur;
            sml_cur = sml_cur->next;
        }else{
            big_cur->next = cur;
            big_cur = big_cur->next;
        }
        cur = cur->next;
    }
    big_cur->next = NULL;
    sml_cur->next = big_head->next;
    return sml_head->next;
}